%% vision_control_server.tex
%% author: Neururer Martin
%% date: 25.11.2009
%% email: martin.neururer@gmail.com
%%
%% this file should be compiled with V2.4 of "sig-alternate.cls" April 2009

\documentclass{sig-alternate}

\usepackage{graphicx}
%\usepackage{chngcntr}
%\usepackage{nicefrac}
%\usepackage{float}
%\usepackage{ccaption}
\usepackage{listings}
\usepackage[symbol]{footmisc}
\usepackage{amssymb, amsmath}

\DeclareMathAlphabet{\mathitbf}{OML}{cmm}{b}{it}
%\def\mathbi#1{\textbf{\em #1}} % optional (variant) ...

\begin{document}

\title{ Motion Tracking of Geometric Figures  }
\subtitle{ [Actual Developement Status]
	\titlenote{
	Further information about the project and the corresponding source code for download are available under:
	\texttt{http://code.google.com/p/visioncontrolserver/}.}
}

\numberofauthors{1}
\author{
% 1st. author
\alignauthor
	Neururer Martin\\
	\affaddr{Instituto Tecnol\'ogico de Buenos Aires}\\
	\affaddr{Buenos Aires, Argentina}\\
	\email{mneurure@alu.itba.edu.ar}
}

\maketitle
\begin{abstract}
The program was developed for the purpose of recognising simple geometric patterns that are attached on the top panels of some moving robots. It recognizes two different types of geometric figures, rectangles and acute-angled triangles. Using an arbitrary USB camera which is mounted on a bar, the program determines within the visual range the position and orientation of the moving figures. The plan is to use this program as a server program which sends the current calculated position and orientation values of the objects to some clients. This is useful in robotic competitions or in laboratory experiments to supervise and control several robots in a specified environment. The server program is written in the programming language C and works in real-time.
\end{abstract}

\keywords{computer vision, pattern recognition, motion control}

\section{Introduction}

In many robotic competitions and also in scientific experiments with robots it is useful to apply programs for observing and supervizing robots that do not manipulate their behavior.
The motivation in this project was to write a small and efficient program, that recognizes simple geometric shapes attached on the top panels of the robots.\\
With the help of the geometric shapes it is possible to determine the current position and the orientation of the robots. Generally it is sufficient to use rectangles and triangles to locate the position and the corresponding orientation.\\
The goal was to determine, if the position and orientation of brightly colored shapes (with unknown dimensions) on a dark plane could be accurately resolved by a computer vision system in real-time. To have a high contrast and less noise in the image we uesd in our project white rectangles and acute-angled triangles on a black plane. Furthermore the vision system must be able to find out the position of the geometric shapes even if they are moving in real-time.

\section{Tools and Methods}
\subsection{The OpenCV Library}

To develop the motion tracking system we used already implemented image processing algorithms from the open source library OpenCV. OpenCV (Intel\textsuperscript{\textregistered} Open Source Computer Vision) is a real time computer vision library written in C and C++ and has also active developements on interfaces for Ruby, Python and Matlab.

\subsubsection{Why OpenCV?}

OpenCV is a cross-platform middle-to-high level API and does not rely on external numerical libraries. It runs under Linux, Windows and Mac OS X. The library is under a BSD licence and is free for both academic (non-commercial) and commercial use.
It offers more than 500 functions that are span in many areas in image processing, motion tracking, medical imaging, camera calibration, robtics, machine learning and other vision fields \cite{Brad2008}.\\\\
Furthermore OpenCV was designed for computationally efficiency with a strong focus on real time applications. The OpenCV library is written in performance-optimized C/C++ code and can be run in multiple threads (if OpenCV is built with OpenMP support) to take advantage of the actual multi-core processors. Additionally provides OpenCV an interface to the Intel\textsuperscript{\textregistered} Integrated Performance Primitives (IPP) library \cite{Pisa2007, Brad2008}. This is a commercial low-level library for matrix computation, signal and image processing developed by the Intel Corporation. The library offers functions and low-level routines that are optimized to run on Intel Processors. Using the IPP library will boost up the performance of the application between approximately 30\% and 50\% (depends on the design of the implementation) \cite{Stav2005}. If the library is installed on the machine, OpenCV will automatically load the appropriate IPP library at runtime.\\
A further advantage of using OpenCV is, it has internally a built-in camera library and supports a lot of standard Firewire and USB cameras.

\subsection{Used Developement Tools}

The system was developed under Mac OS X 10.5.8, Leopard. To build the program we used CMake (version 2.8.0), an open source cross-platform build system generator and the GCC compiler 4.0.1 (build 5493) from Apple. We decided us to use CMake, because it makes the program applicable on different systems. It generates native makefiles and workspaces that can be used in the compiler environment of the current platform. For capturing the images and testing the scenes we used a standard USB color camera with a resolution of 640x480 pixles and the built-in iSight camera of the MacBook.
At the beginning of the developement we used for testing the scenes a black carton plane as background and a white rectangular carton strip (later also triangles).

\section{Current Development Status}

At present, the development of the project is not completed. The elaboration of the filter algorithm to recognize rectangles is still in progress and the perceiving method for triangles is not implemented yet.
To implement the program we are using currently the OpenCV library of version 1.0.0 available as a port file package from MacPorts (this will being changed in next time). For image processing we captured the images of the current camera with the given functions of OpenCV.\\
In order to find the white rectangle on the black panel we have at first to change the captured image into a grayscale image.
Afterwards we remove the noise in the image by transforming it into a bi-level (binary) image. This will be done with two image processing operations of OpenCV:
\begin{enumerate}
	\item smoothing the image with the $3\times 3$ -- \textit{Gaussian averaging operator} to reduce the response to noise (\textit{low-pass filter}),
	%\item filtering out the pixels with too large values and create the binary image (in black and white) by using the \textit{uniform threshold operator} with a brightness threshold value of 160.
	\item create the binary image in black and white by using the \textit{uniform threshold operator} with a brightness threshold value of 160 (filtering out the pixels with too large values).
\end{enumerate}
%For the edge detection we used the \textit{Canny edge detection operator} from the OpenCV library.
To detect the edeges we used the \textit{Canny edge detection operator} from the OpenCV library.
The Canny algorithm is very accurate and has an optimal detection with very minimal spurious responses. Furthermore the algorithm is very robust and has a minimal response, that means it eleminates multiple responses to a single edge.\\\\
For detecting the straight lines of the white experimental rectanlge, we used the \textit{Progressive Probabilistic Hough Transform} (PPHT). The PPHT method is available in OpenCV with the function \texttt{cvHoughLines2} and the corresponding parameter \texttt{CV\_HOUGH\_PROBABILISTIC}. The PPHT has the advantage, compared to the Standard Hough Transform (SHT) and the Probablistic Hough Transform (PHT), that it minimises the amount of computation needed to detect the lines \cite{Mat1999}. The algorithm exploits the difference in the fraction of votes needed to detect reliably the (imperfect) straight lines. The voting process reduces the computation significantly and makes the algorithm ideal for real-time applications like tracking.
Figrue \ref{fig:detected_segm} shows the output of the Canny algorithm and the detected line segments (drawn in a different colors) with the PPHT.

\begin{figure}[ht]
	\centering
	%\includegraphics[width=0.50\textwidth]{graphics/capt_img.png}
	\includegraphics[scale=0.35, trim=100 30 100 10]{graphics/img_canny2.png}
	% capt_img.png: 720x582 pixel, 72dpi, 25.40x20.53 cm, bb=0 0 720 582
	\caption{\protect\small Result of the Canny edge detection algorithm and the detected line segments (colored lines) that forms right angles.} %Detected line segments that forms a rectangle.}
	\label{fig:detected_segm}
\end{figure}

\subsection{Finding the Object}

In order to find the line segments of the white rectangle in the picture one has to analyze the data of all the line segments found by the Hough transform.\footnote[2]{Mainly we analyzed the data in the same way as described in the paper of J. Katrasnik \cite{Kat2007}.}\\
As described in the paper of J. Katrasnik \cite{Kat2007}, to find the line segments that form the searched rectangle it is necessary to define some parameters that chraracterize a right angle formed by two line segments.
The data of all line segments (as desribed in the paper \cite{Kat2007}) are being analyzed in following steps:
\renewcommand{\labelitemi}{$-$}
\begin{itemize}
	\item At first are being calculated the angles (\textit{orientation}) that the line segments form with the x-axis of the image.\\
	The calculation of the orientation angle will be done in the source code as shown below in listing \ref{lis:orient_angle}.

	\lstset{
		language = [ANSI]C,
		basicstyle = \scriptsize,
		frame = single,
		tabsize = 2,
		captionpos = b,
		breaklines = true,
		breakatwhitespace = true,
		morekeywords = {atan2, CvPoint}
	}
	\renewcommand{\lstlistingname}{\protect\small Listing}
	\begin{lstlisting}[caption={\protect\small Calculation of the orientation angle.}, label=lis:orient_angle]
	/* distances between the points A and B */
	dDist_x = pPtB->x - pPtA->x;
	dDist_y = pPtB->y - pPtA->y;
	/* angle (orientation) of the current line segment */
	dAngle = atan2(dDist_y, dDist_x)*(180.0f/M_PI);
	\end{lstlisting}

	\item Afterwards compare these orientation angles with one another by calculating the difference between two angles.\\
	If the difference between two angles is $90 \pm tolerance$ degrees\footnote[3]{In our case we used a tolerance value of 2 degrees.}, the following parameters that characterizing a right angle between two line segments are being calculated (see also \cite{Kat2007}):
	\renewcommand{\labelitemii}{$\diamond$}
	\begin{itemize}
		\item the \textit{shortest distance} between the ends of the line segments,
		\item the \textit{angle} between the line segments,
		\item the \textit{length} of both line segments,
		\item the \textit{orientation of the angle} (to the x-axis) that the line segments are forming,
		\item the \textit{position of the vertex} of this angle (intersection point of both line segments)
	\end{itemize}
	These parameters are being stored into a data structure representing a right angle as shown in listing \ref{lis:param_struct}.
	The right angle structure self, will be added to a dynamic array with a maximal size of 1200 elements to keep small the amount of memory. With this size it is theoretically possible to store the information of 300 rectangles or 400 triangles. This is more than sufficient as normally required.

	\begin{lstlisting}[caption={\protect\small Parameter structure to represent a right angle between two line segments (data size: 48 bytes).}, label=lis:param_struct]
	typedef struct param {
		double dMinDist; /* shortest distance */
		double dAngle; /* angle between the line segments */
		double dLineLength[2]; /* length of both line segments */
		double dAngleOrient; /* orientation of the angle */
		CvPoint vertexPos; /* position of the vertex */
	} rightAngle;
	\end{lstlisting}

	\item  If the orientation and the vertex value in multiple right angle structures are very close together, then \textit{average} these right angles (except their lengths) and remove unnecessary line segments.\medskip\\
	%If multiple right angle structures have nearly the same orientation and vertex value, then all values are being averaged except the length of the line segments.\\
	It is possible, that several right angle structures have nearly the same orientation and vertex points. This can be happen if one edge of a rectangle was not well recognized by the system and is represented by multiple-segment sections. In this case \textit{all parameters} of the right angles are being averaged \textit{except the length of the two line segments}; instead the \textit{longest lengths} will be kept.
	\begin{itemize}
		\item The next step is to remove those right angle elements from the dynamic array which are superfluous.\\
		Those right angle structures that have the \textit{smallest distance values} between the ends of the line segments and are  \textit{longer than the half} of the longest line segment, can not be a part of the rectangle (they are a lines of other rectangles or are false positive line segments) -- hence, they are being eleminated.
	\end{itemize}
\end{itemize}
We used until here the same analyzation and filtration approaches as described in the paper of Katrasnik \cite{Kat2007}.
Afterwards are our requirements different and the further line selection methods will be done in an other way.
But this part is not implemented yet.

\subsubsection{Used Formulas}

As explained in the first step of the data analyzation prozess, the \textit{orientation angles} that the \textsl{line segments} and also the \textsl{right angles} forms with the x-axis were calculated with the \texttt{atan2} method of the standard library (see listing \ref{lis:orient_angle}). The remaining parameters of the right angle structure were calculated as following:
\begin{description}
	\item[\protect\small Angle between line segments:] The enclosed \textit{angle} $\alpha$ of two line segments $a$ and $b$ was calculated by transformation of the \textit{Cauchy-Schwarz inequality} such that,
		$$\cos\alpha = \dfrac{\langle a,b\rangle}{\|a\| \cdot \|b\|}.$$
	\item[\protect\small Length of a line segment \textbf{\textit{a}}:] This was done by the \textit{Euclidean norm} such that,
		$$\|a\| =\sqrt{\langle a, a\rangle}.$$
	\item[\protect\small Vertex position:] The calculation of the vertex position was done by calculating the \textit{intersection point} between two line segments $a$ and $b$. The result can be calculated with a simple and fast method for 2D-lines by solving a \textit{linear equation system} using the \textit{rule of Cramer}:
	\begin{enumerate}
		\item get the vectors from the line points $\mathitbf{p}_1, \mathitbf{p}_2, \mathitbf{p}_3$ and $\mathitbf{p}_4$:
			$$
				\begin{align}
					&	\mathitbf{a} = \mathitbf{p}_2 - \mathitbf{p}_1, \\
					&	\mathitbf{b} = \mathitbf{p}_4 - \mathitbf{p}_3 \quad\textnormal{and}\\
					& \mathitbf{c} = \mathitbf{p}_1 - \mathitbf{p}_3.
				\end{align}
			$$
		\item calculate the determinate 
			$$
					D = \begin{vmatrix}
										a_1 & b_1 \\
										a_2 & b_2
						\end{vmatrix} = a_1 b_2 - b_1 a_2,
			$$
		\item calculate the fraction values $s_a$ and $s_b$ with the answer vector $\mathitbf{c}$ such that,
			$$
				\begin{align}
						& s_a = \dfrac{
											\begin{vmatrix}
												c_1 & b_1 \\
												c_2 & b_2
											\end{vmatrix}}{D} = \dfrac{1}{D}(c_1 b_2 - b_1 c_2)\quad\textnormal{and}\\
						& s_b = \dfrac{
											\begin{vmatrix}
												a_1 & c_1 \\
												a_2 & c_2
											\end{vmatrix}}{D} = \dfrac{1}{D}(a_1 c_2 - c_1 a_2).
				\end{align}
			$$
		\item solve the equations
				$$
						\begin{align}
							& \mathitbf{p}_a = \mathitbf{p}_1 + s_a (\mathitbf{p}_2 - \mathitbf{p}_1)\\
							& \mathitbf{p}_b = \mathitbf{p}_3 + s_b (\mathitbf{p}_4 - \mathitbf{p}_3)
						\end{align}
				$$
				so that $\mathitbf{p}_a = \mathitbf{p}_b$ and get the intersection point $(x, y)$ by subsequent substitution of the resulting equations such that, %substitution of the corresponding equations with unknowns such that
				$$
					\begin{align}
						& x = x_1 + s_a \underbrace{(x_2 - x_1)}_{a_1}\quad\textnormal{and}\\
						& y = y_3 + s_b \underbrace{(y_4 - y_3)}_{b_2}.
					\end{align}
				$$
	\end{enumerate}
	\item[\protect\small Shortest distance:] At the moment the \textit{shortest distance} between the ends of the line segments was calculated by calculating all \textit{differences} between the \textsl{x-coordinates} and the \textsl{y-coordinates} of the end points and searching their minimum afterwards.\\
	But this is not sufficient and correct and will be changed in next time.
\end{description}

\subsection{Actual Results and Problems}

At the current stage of the developement, the program recognices very well those line segments that are forming right angles (see figure \ref{fig:detected_segm}). But during the test phase of the program with the white rectangle and the black plane were rising up some difficulties.\\
The first problem was, that the intensity of the daylight and also the efficacies of the lamps are different.
This leads, that in the captured images were often regions with different ranges of intensities (caused by reflections or shadows). Generally, the uniform threshold method is inapplicable for different (i.e. high) light intensities. In the worst case, the rectangle will not completely found. This problem will be solved in the next time by replacing the single threshold method \texttt{cvThreshold} with the \textit{adaptive (dynamic) threshold} method \texttt{cvAdaptiveThreshold}.\medskip\\
The next problem was the memory fragmentation. As discussed in the internet \cite{gma2008}, causing the methods \texttt{cvFindContours} and \texttt{cvHoughLines2} a significantly amount of fragmentations. We have analyzed the memory usage of the program with \textit{Memcheck} (embedded in Valgrind) and also with the tools \textit{MallocDebug} and \textit{ObjectAlloc} from the Xcode-Package of Apple. We have found out, that the memory allocation of the program was rising linearly over time -- slowly, but continuous (see figure \ref{fig:mem_alloc}).

\begin{figure}[ht]
	\centering
	%\includegraphics[width=0.50\textwidth]{graphics/mem_alloc.png}
	\includegraphics[scale=0.24, trim=100 40 100 10]{graphics/mem_alloc.png}
	% mem_alloc.png: 1080x785 pixel, 72dpi, 38.10x27.69 cm, bb=0 0 1080 785
	\caption{\protect\small \textit{ObjectAlloc} to analyze the memory life-cycles of process' allocated blocks.}
	\label{fig:mem_alloc}
\end{figure}

We verified the source code if all allocated memory blocks are being freed after using. As mentioned in the web \cite{gma2008} and also in the reference manual of OpenCV \cite{OpCV2009}, the probability of memory fragmentation can be decreased by using a \textsl{larger} block size ($\gg 64000$ bytes) in the function \texttt{cvCreateMemStorage} and by increasing the \textit{sequence block size} ($\gg 1000$ bytes), using the method \texttt{cvSetSeqBlockSize}, to affect the memory allocation granularity. Maybe it is also adequate to call the methods \texttt{cvReleaseMemStorage} and \texttt{cvCreateMemStorage} on each iteration step, to make sure that the memory allocation is not rising.\medskip\\
A further problem was also that the program did not well recognized the object if it was moving faster in the test area.
Hence, not all edges of the test rectangle were found as shown in figure \ref{fig:im_not_all_edges}.
Perhaps this problem can be overcome in future by increasing the shutter speeds of the camera and additionally increasing the system's overall speedup by using the parallelization technique of OpenMP or the IPP library of Intel.

\begin{figure}[ht]
	\centering
	\includegraphics[scale=0.35, trim=100 30 100 10]{graphics/img_not_all_edges.png}
	% img_not_all_edges.png: 720x582 pixel, 72dpi, 25.40x20.53 cm, bb=0 0 720 582
	\caption{\protect\small Captured image of the moved rectangle.}
	\label{fig:im_not_all_edges}
\end{figure}

\section{Conclusion}

The \textit{Progressive Probabilistic Hough Transform} algorithm is a very efficient method to detect line segments in an image and reducing the amount of computation steps significantly. Compared with the \textit{contour processing methods} (\texttt{cvFindContours} and \texttt{cvApproxPoly}) in OpenCV, the PPHT method is a very good alternative to find the contours of geometric figures. In general, the performance of the PPHT method and of the contour processing methods depends strong on the complexity of the given task and is difficult to say wich method is better. To compare the performance of these methods of OpenCV there exists a small benchmark as described in \cite{Piv2006}.
Furthermore, the PPHT method in OpenCV needs two important parameters:
\begin{itemize}
	\item the \textit{minimum line length} and
	\item the \textit{maximum gap} between the line segments lying on the same line.
\end{itemize}
Since the camera can be mounted at different distances to the objects, the line lengths of the geometric figurs and also the maximum gap threshold are variable. If the minimum line length value is set too small, then the program will produce too much superfluously line segments on the same edges. To keep the number of unnecessary line segments small, we need to adapt these values in relation to the given distance between the camera and the objects -- hence, we need to calibrate the camera.\\
Finally in the newest version of OpenCV (version 2.0.0) were made a lot of bugfixes and optimizations of the image processing operations (i.e. SSE2 optimizations) and are now several times faster. For reasons of stability and performance, it is recommended to change the current used version of OpenCV (v 1.0.0) to the newest version.

%\nocite{*}
\bibliographystyle{abbrv}
\bibliography{vision_control_server}
% That's all folks!
\end{document}
